10_Q_Learning

Tags: #◇CSINTSY #◇Computational Thinking #◇Computer Science #◇Artificial Intelligence #◇Machine Learning #◇Intelligent Systems #◇Probability #◇Data Analysis

---

◇Overview

Q-Learning is a model-free reinforcement learning algorithm.

◇Details / Theory

10. Q-Learning Reviewer

◇Overview

Q-Learning is a model-free reinforcement learning algorithm.
Model-Free: It does not need to know the Transition Probability ($T$) or Reward Function ($R$) of the environment beforehand. It learns by trial and error. Goal: To learn the Q-Function (Quality Function), which estimates the value of taking a specific action in a specific state.

◇The Q-Function: $Q(s, a)$

Represents the expected cumulative future reward of taking action $a$ in state $s$, and then acting optimally afterwards. Once we know $Q(s, a)$ for all states and actions, the optimal policy is simply to pick the action with the highest Q-value in each state:
$\pi^\*(s) = \text{argmax}\_a Q(s, a)$

◇The Q-Table

A table (matrix) where rows are States and columns are Actions. Each cell contains the value $Q(s, a)$. Initialized to 0 (or random values). Updated iteratively as the agent interacts with the environment.

◇Q-Learning Update Rule (Bellman Update)

When the agent is in state $s$, takes action $a$, receives reward $R$, and lands in new state $s'$, we update the Q-value:

$Q(s, a) \leftarrow Q(s, a) + \alpha [ \underbrace{R + \gamma \max_{a'} Q(s', a')}_{\text{Target}} - \underbrace{Q(s, a)}_{\text{Current}} ]$

Components:

1. $Q(s, a)$: The current estimated value (Old Value).
2. $\alpha$ (Alpha): Learning Rate ($0 < \alpha \le 1$).
   Determines how much new information overrides old information.
   High $\alpha$: Learn fast, but volatile.
   Low $\alpha$: Learn slow, but stable.
3. $R$: Immediate reward received.
4. $\gamma$ (Gamma): Discount Factor ($0 \le \gamma \le 1$). Importance of future rewards.
5. $\max_{a'} Q(s', a')$: The estimate of optimal future value from the next state $s'$. We assume we will take the best action from there.
6. Temporal Difference (TD) Error: The term in the brackets $[Target - Current]$. It represents the difference between what we expected and what actually happened.

◇Exploration vs. Exploitation

How does the agent choose actions while learning?
Exploration: Trying new or random actions to discover their rewards. Necessary to find better paths. Exploitation: Choosing the action currently known to be the best (highest Q-value) to maximize reward.

Epsilon-Greedy Strategy ($\epsilon$-greedy)

A common method to balance exploration and exploitation.
With probability $\epsilon$ (epsilon): Explore (choose a random action). With probability $1 - \epsilon$: Exploit (choose the best action from Q-table). Usually, $\epsilon$ starts high (explore a lot) and decays over time (exploit more as we learn).

◇Solved Example: Q-Value Update

Scenario:
Current State ($s$): Room A. Action ($a$): Move to Room B. Reward ($R$): +10 (Found a coin). Next State ($s'$): Room B. Current Q-Value $Q(A, \text{Move B})$: 5. Best Q-Value in Next State $\max Q(B, a')$: 20 (Maybe Room B is close to exit). Learning Rate ($\alpha$): 0.1. Discount Factor ($\gamma$): 0.9.

Calculation:

1. Target Value:
   $R + \gamma \max Q(s', a')$
   $10 + 0.9(20) = 10 + 18 = 28$

2. Difference (TD Error):
   $\text{Target} - \text{Current}$
   $28 - 5 = 23$

3. New Q-Value:
   $Q(s, a) + \alpha [\text{Difference}]$
   $5 + 0.1 [23]$
   $5 + 2.3 = 7.3$

Result: The Q-value for moving from A to B increased from 5 to 7.3 because the outcome was better than expected.

---

◇Common Pitfalls

Confusing the learning rate $\alpha$ (how much to update) with the discount factor $\gamma$ (how much to value future rewards). Forgetting that Q-Learning is model-free — it does not need transition probabilities; it learns from experience. Using pure exploitation ($\epsilon = 0$) too early — sufficient exploration is needed for the Q-table to converge.

◇Summary

TL;DR — Q-Learning updates Q-values via $Q(s,a) \leftarrow Q(s,a) + \alpha[r + \gamma \max_{a'} Q(s',a') - Q(s,a)]$. It’s model-free, uses $\epsilon$-greedy for exploration/exploitation balance, and converges to optimal Q-values with sufficient exploration.

◇Links

Related: Source / Reference:

---

Made by 2ru17

Please contact me through discord or my the university email for any problems regarding the reviewer. Thanks!

◇References & Navigation

• Previous Topic: ◇MDP
• Related Notes: ◇Q-Learning